package leetcode;

import data_structur.Sort.SortDemo;

import java.io.UnsupportedEncodingException;
import java.util.*;

public class Test {

    public static int[] twoSum(int[] nums, int target) {

        for(int i = 0; i < nums.length; i++){
            int need = target - nums[i];
            for(int j = i + 1; j < nums.length; j++){
                if(nums[j] == need){
                    return new int[]{i, j};
                }
            }
        }
        return new int[0];
    }

    public static int reverse(int x) {
        int result = 0;
        try {
            while (x != 0) {
                result = result * 10 + x % 10;
                x = x / 10;
            }
        }catch (Exception e){
            return 0;
        }
        return result;
    }

    public static String replaceSpace(String s){
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char temp = s.charAt(i);
            if (temp == ' '){
                sb.append("%20");
            } else {
                sb.append(temp);
            }
        }
        return sb.toString();
    }

    public static int[] reversePrint(ListNode head) {
        ListNode temp = head;
        int size = 0;
        while (temp != null){
            size++;
            temp = temp.next;
        }
        int[] res = new int[size];
        temp = head;
        for (int i = size - 1; i >= 0; i--){
            res[i] = temp.val;
            temp = temp.next;
        }
        return res;
    }

    // 重构树
    private static final Map<Integer, Integer> inorderMap = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int lengthOfInOrder = inorder.length;
        for (int i = 0; i < lengthOfInOrder; i++) {
            inorderMap.put(inorder[i], i);
        }

        return this.myBuild(preorder, inorder, 0, lengthOfInOrder -1, 0, lengthOfInOrder - 1);
    }

    public TreeNode myBuild(int[] preorder, int[] inorder, int pre_left, int pre_right, int in_left, int in_right){
        if (pre_left > pre_right) return null;

        // 前序遍历的第一个节点就是根节点
        int pre_root = pre_left;
        // 在中序遍历中定位根节点
        int in_root = inorderMap.get(preorder[pre_root]);

        // 创建根节点
        TreeNode rootNode = new TreeNode(preorder[pre_root]);

        // 得到左子树中的节点个数
        int left_size = in_root - in_left;

        rootNode.left = myBuild(preorder, inorder, pre_left + 1, pre_left + left_size, in_left, in_root - 1);
        rootNode.right = myBuild(preorder, inorder, pre_left + left_size + 1, pre_right, in_root + 1, in_right);
        return rootNode;
    }

    public boolean exist(char[][] board, String word) {
        char[] charWord = word.toCharArray();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (findChar(board, charWord, i, j, 0)) return true;
            }
        }
        return false;
    }
    public boolean findChar(char[][] board, char[] word, int x, int y, int index){
        if (x >= board.length || y >= board[0].length || x < 0 || y < 0  ||board[x][y] != word[index]) return  false;
        if (index == word.length - 1) return true; // 这俩相等说明遍历完了，开始回溯
        board[x][y] = '\0';
        boolean res = findChar(board, word, x + 1, y, index + 1) ||
                findChar(board, word, x - 1, y, index + 1) ||
                findChar(board, word, x, y + 1, index + 1) ||
                findChar(board, word, x, y - 1, index + 1);
        board[x][y] = word[index];
        return res;
    }

    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 方法一：快慢指针
//        ListNode pre = new ListNode(-1, head);
//        ListNode fast = head;
//        ListNode slow = pre;
//
//        int pace = 0;
//        while(pace < n){
//            fast = fast.next;
//            pace++;
//        }
//
//        while(fast != null){
//            fast = fast.next;
//            slow = slow.next;
//        }
//
//        slow.next = slow.next.next;
//
//        return pre.next;

        // 方法二 先计算长度
        ListNode pre = new ListNode(-1, head);
        ListNode cur = head;
        ListNode cur2 = pre;

        int size = 0;
        while (cur != null){
            cur = cur.next;
            size++;
        }

        for (int i = 0; i < size - n; i++) {
            cur2 = cur2.next;
        }
        cur2.next = cur2.next.next;

        return pre.next;
    }

    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null)
            return head;

        ListNode dummy = new ListNode(-1, head);
        ListNode temp = dummy;
        while(temp.next != null && temp.next.next != null){
            ListNode pre = temp.next;
            ListNode cur = temp.next.next;
            temp.next = cur;
            pre.next = cur.next;
            cur.next = pre;
            temp = pre;
        }

        return dummy.next;
    }

    public ListNode removeDuplicateNodes(ListNode head) {
        Map<Integer, Integer> map = new HashMap<>();
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode temp = dummy;

        while (temp.next != null){ // dummy - 1 - 2 - 3 - 3 - 2 - 1
            if (map.containsKey(temp.next.val)) {
                temp.next = temp.next.next;
            } else {
                map.put(temp.next.val, 0);
                temp = temp.next;
            }
        }

        return dummy.next;
    }

    public String reverseWords(String s) {
        StringBuilder res = new StringBuilder();
        StringBuilder seg = new StringBuilder();
        int size = s.length();
        for (int i = size - 1; i >= 0; i--) {
            char cur = s.charAt(i);
            if (cur == ' ') {
                res.insert(0, " " + seg);
                seg = new StringBuilder();
            } else if (i == 0) {
                res.insert(0, seg.append(cur));
            } else {
                seg.append(cur);
            }
        }
        return res.toString();
    }

    /**
     * 判定输入的是否是汉字
     *
     * @param c
     *      被校验的字符
     * @return true代表是汉字
     */
    public static boolean isChinese(char c) {
        Character.UnicodeBlock ub = Character.UnicodeBlock.of(c);
        if (ub == Character.UnicodeBlock.CJK_UNIFIED_IDEOGRAPHS
                || ub == Character.UnicodeBlock.CJK_COMPATIBILITY_IDEOGRAPHS
                || ub == Character.UnicodeBlock.CJK_UNIFIED_IDEOGRAPHS_EXTENSION_A
                || ub == Character.UnicodeBlock.GENERAL_PUNCTUATION
                || ub == Character.UnicodeBlock.CJK_SYMBOLS_AND_PUNCTUATION
                || ub == Character.UnicodeBlock.HALFWIDTH_AND_FULLWIDTH_FORMS) {
            return true;
        }
        return false;
    }

    /**
     * 校验String是否全是中文
     *
     * @param name
     *      被校验的字符串
     * @return true代表全是汉字
     */
    public static boolean checkNameChinese(String name) {
        boolean res = true;
        char[] cTemp = name.toCharArray();//转换为数组
        for (int i = 0; i < name.length(); i++) {
            if (!isChinese(cTemp[i])) {//逐个判断是否为中文
                res = false;
                break;
            }
        }
        return res;
    }

    public boolean isPowerOfTwo(int n) {
        if (n == 1) return true;
        if (n % 2 == 1) {
            return false;
        } else {
            return isPowerOfTwo(n / 2);
        }
    }

    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> father = new ArrayList<>();
        father.add(new ArrayList<>());
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            int n = nums[i];
            for (int j = 0; j < Math.pow(2, i); j++) {
                List<Integer> son = father.get(j);
                son.add(n);
                father.add(son);
            }
        }
        return father;
    }

    public boolean judgeSquareSum(int c) {
        long a = 0;
        long b = (long) Math.sqrt(c);

        while (a <= b) {
            long sum = a * a + b * b;
            if (sum == c) {
                return true;
            } else if (sum < c) {
                a++;
            } else {
                b--;
            }
        }

        return false;
    }

    // 向右旋转k次链表
    public ListNode rotateRight(ListNode head, int k) {
        if (k==0 || head == null || head.next == null) return head;

        ListNode slow = head;// slow本身是旋转后的结尾，slow的下一个是旋转后的头节点
        ListNode fast = head;

        int len = 0;
        while (fast != null) {
            fast = fast.next;
            len++;
        }

        k = k % len;

        if (k == 0) {
            return head;
        }

        fast = head;
        while (k != 0) {
            fast = fast.next;
            k--;
        }

        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }

        ListNode dummy = slow.next;
        slow.next = null;
        fast.next = head;

        return dummy;
    }

    // 翻转链表1
    public ListNode reverseListNode(ListNode head) {
        // 头插法，需要新头
        ListNode newHead = null;
        ListNode temp;

        while (head != null) {
            temp = head;
            head = head.next;
            temp.next = newHead;
            newHead = temp;
        }

        return newHead;
    }

    // 翻转链表2
    public ListNode reverseListNode2(ListNode head) {
        // 原地翻转，和头插类似
        ListNode temp = head;
        ListNode next = head.next;
        Set<Integer> set = new HashSet<>();

        while (next != null) {
            temp.next = next.next;
            next.next = head;
            head = next;
            next = temp.next;
        }

        return head;
    }

    // 1893 检查覆盖
    public boolean isCovered(int[][] ranges, int left, int right) {
        int[] arr = new int[50];
        for (int[] range : ranges) {
            for (int n = range[0]; n <= range[1]; n++) {
                arr[n - 1] = 1;
            }
        }
        for (int k = left; k <= right; k++) {
            if (arr[k - 1] < 1) return false;
        }
        return true;
    }

    public static void main(String[] args) {
//        int[] pre = {3,9,20,15,7};
//        int[] in = {9,3,15,20,7};
        Test t = new Test();
//        TreeNode tn = t.buildTree(pre, in);
//        System.out.println(tn);
        int[][] ranges = {{1, 10}, {10, 20}};
        boolean covered = t.isCovered(ranges, 21, 21);
        System.out.println(covered);
//        ListNode l1 = new ListNode(0);
//        ListNode l2 = new ListNode(1);
//        ListNode l3 = new ListNode(2);
//        ListNode l4 = new ListNode(3);
//        ListNode l5 = new ListNode(4);
//        ListNode l6 = new ListNode(1);
//        l1.next = l2;
//        l2.next = l3;
//        l3.next = l4;
//        l4.next = l5;
//        System.out.println(l1);
//        l5.next = l6;
//        t.removeDuplicateNodes(l1);
//        String s = "Let's take LeetCode contest";
//        System.out.println(t.reverseWords(s));
//        System.out.println(t.isPowerOfTwo(6));
//        System.out.println(t.judgeSquareSum(2));
//        System.out.println(t.reverseListNode2(l1));
    }
}
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }

    @Override
    public String toString() {
        return "ListNode{" +
                "val=" + val +
                ", next=" + next +
                '}';
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }

    @Override
    public String toString() {
        return "TreeNode{" +
                "val=" + val +
                ", left=" + left +
                ", right=" + right +
                '}';
    }
}


